package demo1;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-28
 * Time: 7:55
 */

class Solution {
    public List<List<Integer>> ret = new ArrayList<>();
    public LinkedList<Integer> list= new LinkedList<>();
    public void backTracking(int[] nums,boolean[] used){
        if(list.size()==nums.length){
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i =0;i<nums.length;++i){
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false) continue;
            if(used[i]==false){
                used[i] = true;
                list.add(nums[i]);
                backTracking(nums,used);
                list.removeLast();
                used[i] = false;
            }
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums.length==0){
            return ret;
        }
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        backTracking(nums,used);
        return ret;
    }
}
public class TestDemo {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,1,2};
        solution.permuteUnique(nums);
        StringBuilder stringBuilder = new StringBuilder();

    }
}
